package leetcode.code0891;

import java.util.Arrays;

public class Solution2 {

	int mod = (int) 1e9 + 7;

	public int sumSubseqWidths(int[] nums) {
		Arrays.sort(nums);
		long ans = 0;
		Long[] dp = new Long[nums.length];
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			ans += (pow(i, dp) - pow(nums.length - i - 1, dp)) * num;
			ans %= mod;
		}
		return (int) ans;
	}

	private long pow(int pow, Long[] dp) {
		if (pow == 0) {
			return 1;
		}
		if (pow == 1) {
			return 2;
		}
		if (dp[pow] != null) {
			return dp[pow];
		}
		long ans = pow(pow >> 1, dp);
		ans *= ans;
		ans %= mod;
		if ((pow & 1) == 0) {
			dp[pow] = ans;
		} else {
			dp[pow] = (ans * 2) % mod;
		}
		return dp[pow];
	}

}
